package hoaitt.vnu.edu.problem7;

import java.util.ArrayList;

public class FindPrimeNumberth {

	/**
	 * Kiểm tra 1 số , có là số nguyên tố hay khonong.
	 * Thuat toan la: 
	 * 1. ktra so do co = 2 khong. true-> return true
	 * 2. Neu khong, ktra n % 2 == 0?
	 * - false
	 * - neu khong, tang len, ktra co chia het cho 3, ...n khong
	 * 3. neu chi chia het cho n thi dung, else sai /
	 * @param number
	 * @return
	 */
	public boolean checkPrime(int number) {
		boolean check = false;

		if (number == 2) {
			check = true;
		} else {
			for (int i = 2; i < number; i++) {
				if (number % i == 0) {
					check = false;
					return check;
				} else {
					check = true;
				}
			}
		}
		return check;
	}

	/**
	 * Kiểm tra 1 số , có là số nguyên tố hay khonong.
	 * Thuat toan la: 
	 * 1. ktra so do co = 2 khong. true-> return true
	 * 2. Neu khong, ktra n % 2 == 0?
	 * - false
	 * - neu khong, tang len, ktra co chia het cho 3, ...n khong
	 * 3. neu chi chia het cho n thi dung, else sai /
	 * @param number
	 * @return
	 */
	public boolean checkPrime1(int number) {
		int limit = (int) Math.sqrt(number);
		for (int i = limit; i > 1; i--) {
			if ((number % i) == 0) {
				if (i == 1) {
					return true;
				} else {
					return false;
				}
			}
		}
		return true;
	}

	public static void main(String[] args) {

		FindPrimeNumberth test = new FindPrimeNumberth();
				System.out.println("Start");
				// long start = System.currentTimeMillis();
				final int MAX = 100000;
		//		for (int i = 0; i < MAX; i++) {
		//			test.checkPrime(i);
		//		}
		//		System.out.println("End" + (System.currentTimeMillis() - start));
		//
				System.out.println("Start");
				long start = System.currentTimeMillis();
				for (int i = 0; i < MAX; i++) {
					test.checkPrime1(i);
				}
				System.out.println("End" + (System.currentTimeMillis() - start));

		//		System.out.println("Start");

		ArrayList<Integer> result = new ArrayList<Integer>(100001);

		int count = 0;
		int value = 2;
		while (count < 100001) {
			if (test.checkPrime1(value)) {
				count = count + 1;
				// System.out.println(value);
			}
			value = value + 1;
		}
		System.out.println(value - 1);

		//				for (int i = 0; i <result.size() ; i++) {
		//					if (test.checkPrime(i)) {
		//						result.add(i);
		//					}
		//				}
		//				
		//				System.out.println(result.get(10000));
		//		System.out.println(result.get(5));
	}
}
